/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package ssp.strategy.agent.util;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;
import ssp.utility.MapValueAscending;

/**
 * Dijkstra法における経路とコストを保持するクラス
 * @author yamazaki
 */
public final class DijkstraTable {

    /**
     * 宛先ノード
     */
    private int dstNodeID;
    
    /**
     * 経路を保持するマップ
     */
    private Map<Integer, Integer> pathTable;
    
    /**
     * コストを保持するマップ
     */
    private Map<Integer, Double> costTable;

    /**
     * コンストラクタ
     * @param dstNodeID 宛先ノード
     */
    public DijkstraTable(int dstNodeID) {
        this.dstNodeID = dstNodeID;
        this.pathTable = new HashMap<>(150);
        this.costTable = new HashMap<>(150);
    }

    /**
     * 保持情報を更新する
     * @param prevNodeID 前ノード
     * @param nextNodeID 次ノード
     * @param cost 次ノードに至るまでのコスト
     */
    public void put(int prevNodeID, int nextNodeID, double cost) {
        pathTable.put(nextNodeID, prevNodeID);
        costTable.put(nextNodeID, cost);
    }

    /**
     * 宛先ノードからのbackward traceにより最短路を生成する
     * @return 最短路
     */
    public List<Integer> bachwardTrace() {
        LinkedList<Integer> result = new LinkedList<>();
        int prevNodeID = dstNodeID;
        
        while(prevNodeID != -1) {
            result.addFirst(prevNodeID);
            prevNodeID = getPrevNode(prevNodeID);
        }
        
        return new ArrayList<>(result);
    }

    /**
     * 指定ノードからbackward traceを行う
     * @param dstNodeID 宛先ノード
     * @return 指定ノードまでの最短路
     */
    public List<Integer> backwardTrace(int dstNodeID) {
        LinkedList<Integer> result = new LinkedList<>();
        int prevNodeID = dstNodeID;
        
        while(prevNodeID != -1) {
            result.addFirst(prevNodeID);
            prevNodeID = getPrevNode(prevNodeID);
        }
        
        return new ArrayList<>(result);
    }

    /**
     * 指定ノードの前ノードを返す
     * @param key ノードID
     * @return 指定ノードの前ノード
     */
    public int getPrevNode(int key) {
        return this.pathTable.get(key);
    }

    /**
     * 未探索リストの内からコストが最小となる次ホップ候補を返す
     * @param currentNode 現在の注目ノード
     * @param closed 探索済みノードリスト
     * @return 次ホップ候補．存在しなければ-1
     */
    public int getNextNode(int currentNode, List<Integer> closed) {
        Map<Integer, Double> open = new HashMap<>(costTable);
        for(int closedNode : closed) {
            open.remove(closedNode);
        }
                
        TreeMap<Integer, Double> tmp = new TreeMap<>(new MapValueAscending(open));
        tmp.putAll(open);

        if(tmp.isEmpty() || tmp.lastEntry().getValue() < getCost(currentNode)) {
            return -1;
        }
        
        for (Entry<Integer, Double> entry : tmp.entrySet()) {
            if (entry.getValue() >= getCost(currentNode)) {
                return entry.getKey();
            }
        }
        return -1;
    }

    /**
     * 宛先ノードを返す
     * @return 宛先ノード
     */
    public int getDstNodeID() {
        return this.dstNodeID;
    }

    /**
     * 指定ノードまでの最短経路におけるコストを返す
     * @param key 宛先ノード
     * @return 最短経路におけるコスト
     */
    public double getCost(int key) {
        if (!this.costTable.containsKey(key)) {
            return Double.MAX_VALUE;
        }
        return this.costTable.get(key);
    }

    /**
     * 宛先ノードまでの最短経路におけるコストを返す
     * @return 最短経路におけるコスト
     */
    public double getResultCost() {
        if(!costTable.containsKey(dstNodeID)) {
            return Double.MAX_VALUE;
        }
        return this.costTable.get(dstNodeID);
    }
}
